import heapq

inf = float('inf')
class MedianFinder:

    def __init__(self):
        self.min = MinHeap()
        self.max = MaxHeap()

    def addNum(self, num: int) -> None:
        mi = self.min.top()
        ma = self.max.top()
        if num <= ma:
            self.max.insert(num)
        else:
            self.min.insert(num)
        while len(self.max) - len(self.min) >= 2:
            self.min.insert(self.max.pop())
        while len(self.min) - len(self.max) >= 2:
            self.max.insert(self.min.pop())

    def findMedian(self) -> float:
        total_length = len(self.min) + len(self.max)
        if total_length & 1:
            if len(self.max) > len(self.min):
                return self.max.top()
            else:
                return self.min.top()
        else:
            return (self.min.top() + self.max.top()) / 2

class MinHeap:
    def __init__(self, l=None):
        if l is None:
            l = []
        self.heap = l
        heapq.heapify(self.heap)

    def insert(self, x):
        heapq.heappush(self.heap, x)

    def pop(self):
        return heapq.heappop(self.heap)

    def __len__(self):
        return len(self.heap)

    def top(self):
        return self.heap[0] if self.heap else inf


class MaxHeap:
    def __init__(self, l=None):
        if l is None:
            l = []
        self.heap = [-x for x in l]
        heapq.heapify(self.heap)

    def insert(self, x):
        heapq.heappush(self.heap, -x)

    def pop(self):
        return -heapq.heappop(self.heap)

    def __len__(self):
        return len(self.heap)

    def top(self):
        return -self.heap[0] if self.heap else -inf
